

//  function TreeNode(val, left, right) {
//      this.val = (val===undefined ? 0 : val)
//      this.left = (left===undefined ? null : left)
//      this.right = (right===undefined ? null : right)
//  }
// /**
//  * @param {number[]} preorder
//  * @param {number[]} inorder
//  * @return {TreeNode}
//  */
// var deduceTree = function(preorder, inorder) {
//     if(preorder.length===0||inorder.length===0)
//         return null
//     return new TreeNode(preorder[0],deduceTree(preorder.slice(1,1+inorder.indexOf(preorder[0])),inorder.slice(0,inorder.indexOf(preorder[0]))),deduceTree(preorder.slice(1+inorder.indexOf(preorder[0])),inorder.slice(1+inorder.indexOf(preorder[0]))))
// };
// preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
// deduceTree(preorder,inorder)

// 新方法相对老方法有两个有点，1.不操作数组，而是索引变换来生成树，极大减小开销。2.使用map存储数组的值，从而将查找根节点在中序遍历中的位置的时间复杂度从O(n)降低到O(1)。
function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}

var deduceTree = function (preorder, inorder) {
    // 构建中序遍历值到索引的映射
    const inorderMap = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }

    // 辅助递归函数
    function buildTree(preStart, preEnd, inStart, inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        // 前序遍历的第一个元素是根节点的值
        const rootVal = preorder[preStart];
        const root = new TreeNode(rootVal);
        // 在中序遍历中找到根节点的位置
        const rootIndexInorder = inorderMap.get(rootVal);
        // 计算左子树的节点数量
        const leftSubtreeSize = rootIndexInorder - inStart;
        // 递归构建左子树
        root.left = buildTree(preStart + 1, preStart + leftSubtreeSize, inStart, rootIndexInorder - 1);
        // 递归构建右子树
        root.right = buildTree(preStart + leftSubtreeSize + 1, preEnd, rootIndexInorder + 1, inEnd);
        return root;
    }

    return buildTree(0, preorder.length - 1, 0, inorder.length - 1);
};

const preorder = [3, 9, 20, 15, 7];
const inorder = [9, 3, 15, 20, 7];
const root = deduceTree(preorder, inorder);
console.log(root);